package com.zp.self.module.level_4_算法练习.数学.位运算;

/**
@author By ZengPeng
 */
public class 力扣_29_两数相除 {
    //测试
    public static void main(String[] args) {
        System.out.println(Integer.MIN_VALUE + (-1));
        System.out.println(Integer.MAX_VALUE + (1));
//        System.out.println(new 力扣_29_两数相除().divide(9, 3));
//        System.out.println(new 力扣_29_两数相除().divide(Integer.MAX_VALUE, 3));
//        System.out.println(new 力扣_29_两数相除().divide(Integer.MIN_VALUE, 3));
//        System.out.println(new 力扣_29_两数相除().divide(10, 3));
//        System.out.println(new 力扣_29_两数相除().divide(7, -3));
//        System.out.println(new 力扣_29_两数相除().divide(1, 1));
//        System.out.println(new 力扣_29_两数相除().divide(2147483647, 1));
    }

    /**
    题目：给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
    返回被除数 dividend 除以除数 divisor 得到的商。
    整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
    
    示例 1:
    输入: dividend = 10, divisor = 3
    输出: 3
    解释: 10/3 = truncate(3.33333..) = truncate(3) = 3
    
    示例 2:
    输入: dividend = 7, divisor = -3
    输出: -2
    解释: 7/-3 = truncate(-2.33333..) = -2
    
    提示：
    被除数和除数均为 32 位有符号整数。
    除数不为 0。
    假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231,  231 − 1]。本题中，如果除法结果溢出，则返回 231 − 1。
    
    分析：【Good】
    1.除数不断翻倍 divisor<<1 ,商从1不断翻倍 ，当 divisor<<1 > dividend 时：dividend -= divisor
        变量：剩余值 dividend、已经减去多少个除数、当前是2的多少次方

     优化： 先减去大的  2的n次方，就不用递归了【开始想递归的，结果Integer是不变量,调用方法内使用时，创建了新值】
    边界值 & 注意点：
        1.全部转换为正数  Math.abs(Integer.MIN_VALUE) 居然还是负数......;
     **/
    public int divide(int dividend, int divisor) {
        if (dividend == 0) return 0;
        if (dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE;
        boolean fu =(dividend ^ divisor) <0;//用异或来计算是否符号相异;
        long dividendL = Math.abs((long) dividend);
        long divisorL= Math.abs((long) divisor);
        long  sum = 0,currentSum = 1;
        long up =divisorL ;
        while (dividendL >= divisorL) {
            if(dividendL>=(up<<1)){
                up =up<<1;
                currentSum=(currentSum<<1);
            }else{
                dividendL -=up;//这里被除数减去了  currentSum个除数
                sum+=currentSum; //
                currentSum = 1;
                up =divisorL;
            }
        }
        return  (int)(fu ? -sum : sum);
    }


}
